package LC;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.TreeMap;

/**
 * @ClassName LC30
 * @Description: TODO
 * @Author hl
 * @Date 2021/4/13
 * @Version V1.0
 **/
public class LC30 {
    public static List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res=new ArrayList<>();
        int wordNum=words.length;
        int len=words[0].length();
        HashMap<String,Integer> map1=new HashMap<>();
        for(int i=0;i<words.length;i++){
            map1.put(words[i],map1.getOrDefault(words[i],0)+1);
        }
        for(int j=0;j<=s.length()-wordNum*len;j++){
            int index=0;
            HashMap<String,Integer> map2=new HashMap<>();
            while(index<wordNum){
                String check=s.substring(j+index*len,j+index*len+len);
                if(map1.containsKey(check)){
                    map2.put(check,map2.getOrDefault(check,0)+1);
                    int num=map2.get(check);
                    if(num>map1.get(check)){
                        break;
                    }
                }else{
                    break;
                }
                index++;
            }
            if(index==wordNum){
                res.add(j);
            }
        }
        return res;
    }

    public static void main(String[] args) {
       String s = "wordgoodgoodgoodbestword" ;
       String []words={"word","good","best","good"};
       List<Integer>res=findSubstring(s,words);
        System.out.println(res.toString());
    }


}
